package org.lql.algo.codecrush.week010;

/**
 * @author: liangqinglong
 * @date: 2025-08-30 15:40
 * @description: LCR 152. 验证二叉搜索树的后序遍历序列 <a href="https://leetcode.cn/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/description/">...</a>
 **/
public class VerifyTreeOrder {
	public boolean verifyTreeOrder(int[] postorder) {
		if (postorder == null || postorder.length == 0) {
			return true;
		}
		return dfs(postorder, 0, postorder.length - 1);
	}

	private boolean dfs(int[] postorder, int start, int end) {
		if (start >= end) {
			return true; // 空树或单节点
		}

		int root = postorder[end];
		int m = start;

		// 找到第一个大于 root 的位置 m
		while (m < end && postorder[m] < root) {
			m++;
		}

		// 检查右子树是否都大于 root
		for (int i = m; i < end; i++) {
			if (postorder[i] < root) return false;
		}

		// 递归左右子树
		return dfs(postorder, start, m - 1) && dfs(postorder, m, end - 1);
	}
}
